package chapter6;

import java.util.LinkedList;

/**
 * @author yuh
 * @date 2018/4/16 20:38
 * @description 树形回溯问题 问题在最外层解决 解决一轮 就里面在变换一轮 递归的结束条件是判断已经走到了最外层 进行处理
 */
public class LetterCombination {

    private static String[] strs = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };

    private static LinkedList<String> linkedList = new LinkedList<>();

    private static void findCombination(String digest, int index, String s) {
        if (digest.length() == index) {
            linkedList.addLast(s);
            return;
        }
        String str = strs[digest.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++) {
            findCombination(digest, index + 1, s + str.charAt(i));
        }
    }

    static void getAllCombinations(String digest){
        findCombination(digest,0,"");
        System.out.println(linkedList);
    }

    public static void main(String[] args) {
        getAllCombinations("23");
    }
}
